Multicell Coordinated Beamforming with Rate Outage Constraint--Part I: Complexity Analysis

摘要

This paper studies the coordinated beamforming (CoBF) design in themultiple-input single-output interference channel, assuming only channeldistribution information given a priori at the transmitters. The CoBF design isformulated as an optimization problem that maximizes a predefined systemutility, e.g., the weighted sum rate or the weighted max-min-fairness (MMF)rate, subject to constraints on the individual probability of rate outage andpower budget. While the problem is non-convex and appears difficult to handledue to the intricate outage probability constraints, so far it is still unknownif this outage constrained problem is computationally tractable. To answerthis, we conduct computational complexity analysis of the outage constrainedCoBF problem. Specifically, we show that the outage constrained CoBF problemwith the weighted sum rate utility is intrinsically difficult, i.e., NP-hard.Moreover, the outage constrained CoBF problem with the weighted MMF rateutility is also NP-hard except the case when all the transmitters are equippedwith single antenna. The presented analysis results confirm that efficientapproximation methods are indispensable to the outage constrained CoBF problem.